/**
 * 35. Search Insert Position
 * https://leetcode-cn.com/problems/search-insert-position/
 */
class SearchInsertPosition {
    /**
     * """
     *
     * 方法：searchInsert
     * 使用二分查找算法在有序数组中寻找目标值的插入位置。如果目标值存在于数组中，则返回其索引；如果不存在，则返回它应当被插入的位置。
     *
     * Args:
     * nums (int[]): 一个升序排列的整数数组。
     * target (int): 目标值，我们希望在数组中寻找其插入位置。
     *
     * Returns:
     * int: 目标值的插入位置索引。
     *
     * Time: O(log n) - 二分查找的时间复杂度是对数级别的。
     * Space: O(1) - 该算法只使用了常数级别的额外空间。
     *
     * """
     */
    public int searchInsert(int[] nums, int target) {
        int left = 0, right = nums.length -1; //[left, right]
        while(left <= right){
            int mid = (left + right) / 2;
            if (nums[mid] < target){
                left = mid + 1; //[mid+1, right]
            } else {
                right = mid - 1; //[left, mid-1]
            }
        }
        return left;
    }
}